We establish a lower bound of $\Omega{(\sqrt{n})}$ on the bounded-errorquantum query complexity of read-once Boolean functions, providing evidence forthe conjecture that $\Omega(\sqrt{D(f)})$ is a lower bound for all Booleanfunctions. Our technique extends a result of Ambainis, based on the idea thatsuccessful computation of a function requires ``decoherence'' of initiallycoherently superposed inputs in the query register, having different values ofthe function. The number of queries is bounded by comparing the required totalamount of decoherence of a judiciously selected set of input-output pairs to anupper bound on the amount achievable in a single query step. We use anextension of this result to general weights on input pairs, and generalsuperpositions of inputs.
展开▼
